
// api排序，取第k-1个
function findKthLargest1(nums, k) {
  if(k >= nums.length || k < 0) throw('k值超出数组长度范围')
  return nums.sort((a, b) => b - a)[k-1]
};

// 暴力循环法（选择排序）
function findKthLargest2(nums, k) {
  if(k >= nums.length || k < 0) throw('k值超出数组长度范围')
  let kTh = 0
  for (let i = 0; i < k; i++) {
    let max =nums[i]
    let position = i
    for (let j = i+1; j < nums.length; j++) {
      if(nums[j] > max) {
        max = nums[j]
        position = j
      } 
    }
    if(i === k-1) kTh = max;
    [nums[i], nums[position]] = [nums[position], nums[i]];
  }
  return kTh
};

// 快速排序变异
function findKthLargest3(nums, left, right, k) {
  if(k >= nums.length || k < 0) throw('k值超出数组长度范围')
  const targetIndex = k -1;
  let partitionIndex = partition(nums, left, right);

  while(partitionIndex !== targetIndex) {
    if(partitionIndex > targetIndex){
      right = partitionIndex - 1
      partitionIndex = partition(nums, left, right)
    } else {
      left = partitionIndex + 1;
      partitionIndex = partition(nums, left, right)
    }
  }
  return nums[partitionIndex]


  function partition(arr, left, right) {
    // 分区操作
    var pivot = left, // 设定基准值（pivot）（基准值位置采用随机，可以提高平均效率）
      index = pivot + 1;
  
    for (var i = index; i <= right; i++) {
      if (arr[i] > arr[pivot]) {
        [arr[i], arr[index]] = [arr[index], arr[i]];
        index++;
      }
    }
    [arr[pivot], arr[index - 1]] = [arr[index - 1], arr[pivot]];
    return index - 1;
  }
}







const nums = [52, 2, 11, 134, 34, 124, 123, 25, 17, 24, 546, 52, 54, 34, 73, 56, 34, 37, 92, 4, 26, 432, 42, 424, 12, 56743, 536, 245, 34523, 342523, 43534, 54, 454, 35245, 52, 214, 53, 7, 3234, 432, 312]

console.log(findKthLargest1(nums.slice(), 10));
console.log(findKthLargest2(nums.slice(), 10));
console.log(findKthLargest3(nums.slice(), 0, nums.length, 10));